IR Generation

• 中间表示（intermediate representation, IR）
  • 编译器的 前端 进行 词法分析、语法分析 和 语义分析，并生成中间表示
  • 编译器的 后端 进行优化，并将表示翻译成机器语言

中间表示树 IR Trees

抽象语法表达式 $\mathrm{A}\mathrm{\_}\mathrm{e}\mathrm{x}\mathrm{p}$

• $\mathrm{E}\mathrm{x}$：“表达式”，表示为 $\mathrm{T}\mathrm{r}\mathrm{\_}\mathrm{e}\mathrm{x}\mathrm{p}$
• $\mathrm{N}\mathrm{x}$：“无结果语句”，表示为 $\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}$ 语句
• $\mathrm{C}\mathrm{x}$：“条件语句”

static Tr_exp Tr_Ex(T_exp ex);
static Tr_exp Tr_Nx(T_stm nx);
static Tr_exp Tr_Cx(patchList trues, patchList falses, T_stm stm);

表达式 $\mathrm{T}\mathrm{\_}\mathrm{e}\mathrm{x}\mathrm{p}$

• $\mathrm{C}\mathrm{O}\mathrm{N}\mathrm{S}\mathrm{T}(i)$：整型常数 $i$
• $\mathrm{N}\mathrm{A}\mathrm{M}\mathrm{E}(n)$：符号常数 $n$
• $\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}(t)$：临时变量 $t$
• $\mathrm{B}\mathrm{I}\mathrm{N}\mathrm{O}\mathrm{P}(o,e_1,e_2)$：对操作数 $e_1$、$e_2$ 施加二元操作符 $o$ 表示的操作
• $\mathrm{M}\mathrm{E}\mathrm{M}(e)$：开始于存储地址 $e$ 的 wordSize 个字节的内容
• $\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(f,l)$：过程调用，以参数表 $l$ 调用函数 $f$
• $\mathrm{E}\mathrm{S}\mathrm{E}\mathrm{Q}(s,e)$：先计算语句 $s$ 以形成其副作用，然后计算 $e$ 作为此表达式的结果
• $\mathrm{M}\mathrm{O}\mathrm{V}\mathrm{E}(\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}t,e)$：计算 $e$ 并将结果送入临时单元 $t$
• $\mathrm{M}\mathrm{O}\mathrm{V}\mathrm{E}(\mathrm{M}\mathrm{E}\mathrm{M}(e_1),e_2)$：计算 $e_1$，由它生成地址 $a$，然后计算 $e_2$，并将计算结果存储在从地址 $a$ 开始的 wordSize 个字节的存储单位中
• $\mathrm{E}\mathrm{X}\mathrm{P}(e)$：计算 $e$ 但忽略结果
• $\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}(e,labs)$
• $\mathrm{C}\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}(o,e_1,e_2,t,f)$：依次计算 $e_1$、$e_2$，生成值 $a$、$b$，然后用关系操作符 $o$ 比较 $a$ 和 $b$；如果结果为 true，则跳转到 $t$，否则跳转到 $f$
  • 关系操作符 $o$ 可以是 LT、GT、LE、GE、EQ、NE...
• $\mathrm{S}\mathrm{E}\mathrm{Q}(s_1,s_2)$：语句 $s_1$ 之后跟随语句 $s_2$
• $\mathrm{L}\mathrm{A}\mathrm{B}\mathrm{E}\mathrm{L}(n)$：定义名字 $n$ 的常数值为当前机器代码的地址

Three-address code

基本块和轨迹

Tree 语言表示的程序和机器语言程序之间存在如下不匹配的情况：

• 在表达式中使用 $\mathrm{C}\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}$ 会使得转移与机器语言的规则不同
  • 机器语言的转移指令在条件为假时是下降至下一条指令
• 在表达式中使用 $\mathrm{E}\mathrm{S}\mathrm{E}\mathrm{Q}$ 会使得子树的不同计算顺序产生不同结果
• 在表达式中使用 $\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}$ 也会使得子树的不同计算顺序产生不同结果
• 在一个 $\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}$ 结点的参数表达式中使用另一个 $\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}$ 结点会出问题

对于任意一颗树，可以将它重写为等价的没有上述任何一种情况的树，转换过程分三步进行：

1. 将一棵树重写成一列不含 $\mathrm{S}\mathrm{E}\mathrm{Q}$ 和 $\mathrm{E}\mathrm{S}\mathrm{E}\mathrm{Q}$ 结点的 规范树
2. 将一列树分组组合成其内不含转移和标号的 基本块 集合
3. 对基本块排序并形成一组 轨迹，轨迹中每一个 $\mathrm{C}\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}$ 之后都直接跟随它的 false 标号

规范树 canonical tree

• 定义具有以下属性的树为规范树
  1. 无 $\mathrm{S}\mathrm{E}\mathrm{Q}$ 或 $\mathrm{E}\mathrm{S}\mathrm{E}\mathrm{Q}$
  2. 每一个 $CALL$ 的父亲不是 $\mathrm{E}\mathrm{X}\mathrm{P}(\dots )$，就是 $\mathrm{M}\mathrm{O}\mathrm{V}\mathrm{E}(\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}t,\dots )$

ESEQ 的转换

将 CALL 移到顶层

$\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}$ 的实现是将它的结果返回到同一个规定的返回值寄存器 $\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}(\mathrm{R}\mathrm{V})$ 中，所以像是 $\mathrm{B}\mathrm{I}\mathrm{N}\mathrm{O}\mathrm{P}(\mathrm{P}\mathrm{L}\mathrm{U}\mathrm{S},\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(\dots ),\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(\dots ))$ 的语句都存在冲突，但是可以使用 重写规则 解决

• 对于 $\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(fun,args)$，替换为 $\mathrm{E}\mathrm{S}\mathrm{E}\mathrm{Q}(\mathrm{M}\mathrm{O}\mathrm{V}\mathrm{E}(\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}t,\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(fun,args)),\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}t)$
• 对于 $\mathrm{M}\mathrm{O}\mathrm{V}\mathrm{E}(\mathrm{T}\mathrm{E}\mathrm{M}\mathrm{P}{t}_{new},\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(f,args))$，不执行替换
• 对于 $\mathrm{E}\mathrm{X}\mathrm{P}(\mathrm{C}\mathrm{A}\mathrm{L}\mathrm{L}(f,args))$，不执行替换

线性语句表

经过上述变换后，将得到一颗树 $s_0^{\prime }$，其中所有的 $\mathrm{S}\mathrm{E}\mathrm{Q}$ 结点都集中在树的顶部，可以将类似 $\mathrm{S}\mathrm{E}\mathrm{Q}(\mathrm{S}\mathrm{E}\mathrm{Q}(a,b),c)$ 的表达式统一转化为 $SEQ(a,SEQ(b,c))$。最终 线性化 为如下形式的表达式：

因为 $\mathrm{S}\mathrm{E}\mathrm{Q}$ 结点完全不提供结构化信息，因此可以认为它只是由语句组成的简单列表

基本块 basic block

• 基本块是语句组成的一个序列，需要满足以下条件
  1. 第一个语句是一个 $\mathrm{L}\mathrm{A}\mathrm{B}\mathrm{E}\mathrm{L}$
  2. 最后一个语句是 $\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}$ 或者 $\mathrm{C}\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}$
  3. 没有其他的 $\mathrm{L}\mathrm{A}\mathrm{B}\mathrm{E}\mathrm{L}$、$\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}$ 或者 $\mathrm{C}\mathrm{J}\mathrm{U}\mathrm{M}\mathrm{P}$
• 可以按任意顺序安排基本块，并且程序执行的结果仍是相同的

轨迹 trace

• 轨迹是在程序执行期间可能连贯执行的语句序列